//对于相同字符，s中相同字符的个数 >= t中相同字符的个数
class Solution {  //滑动窗口 + 哈希表
public:  //小优化：count存储"有效字符"的种类(进窗口后、==、c++ ; 出窗前、==、c--)
    string minWindow(string s, string t) {
    int hash1[128] = {0}, hash2[128] = {0}, kinds = 0;
    for(auto& e : t)  //统计t中字符的频次
        if(hash2[e]++ == 0) kinds++;  //计算t中字符的种类

    int minlen = INT_MAX, begin = -1; //存储起始位置、最小长度
    for(int left = 0, right = 0, count = 0; right < s.size(); right++)
    {
        char in = s[right];  
        if(++hash1[in] == hash2[in]) count++;  //进窗口 + 维护count
        
        while(count == kinds) //判断
        {
            if(right - left + 1 < minlen)  //更新结果
            {
                minlen = right - left + 1;
                begin = left;
            }
            char out = s[left++];
            if(hash1[out]-- == hash2[out]) count--; //维护count + 出窗口
        }
    }
    if(begin == -1)  return "";  //没有符合条件的子串
    else return s.substr(begin, minlen); 
    }
};


//对于相同字符，s中相同字符的个数 >= t中相同字符的个数
class Solution {  //滑动窗口 + 哈希表
public://小优化：count存储"有效字符"的个数(进窗口后、<=、c++ ; 出窗前、<=、c--)
    string minWindow(string s, string t) {
    int hash1[128] = {0}, hash2[128] = {0}, n2 = t.size();
    for(auto& e : t)  hash2[e]++;  //统计t中字符的频次

    int minlen = INT_MAX, begin = -1;  //存储起始位置、最小长度
    for(int left = 0, right = 0, count = 0; right < s.size(); right++)
    {
        char in = s[right];
        if(++hash1[in] <= hash2[in]) count++; //进窗口 + 维护count
        
        while(count == n2) //判断
        {
            if(right - left + 1 < minlen)  //更新结果
            {
                minlen = right - left + 1;
                begin = left;
            }
            char out = s[left++];
            if(hash1[out]-- <= hash2[out]) count--; //维护count + 出窗口
        }
    }
    if(begin == -1)  return ""; //没有符合条件的子串
    else return s.substr(begin, minlen);
    }
};


//对于相同字符，s中相同字符的个数 >= t中相同字符的个数
class Solution {  //滑动窗口 + 哈希表
public:
    bool check(int hash1[], int hash2[]) //判断函数
    {
        for(int i = 0; i < 128; i++)
        {
            if(hash2[i] != 0 && hash1[i] < hash2[i]) return false;
        }
        return true;
    }

    string minWindow(string s, string t) {
    string ret;
    int hash1[128] = {0}, hash2[128] = {0}, len = INT_MAX, start = -1;
    for(auto& e : t)  hash2[e]++; //统计t中字符的频次

    for(int left = 0, right = 0; right < s.size(); right++)
    {
        hash1[s[right]]++;  //进窗口
        while(check(hash1, hash2))  //遍历哈希表进行判断，时间消耗有些大
        {
            if(len > right - left + 1) //更新结果
            {
                start = left; 
                len = right - left + 1;
            }
            hash1[s[left++]]--;  //出窗口
        }
    }
    if(len != INT_MAX)  return ret = s.substr(start, len);  
    else return "";  //没有符合条件的子串
    }
};